home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 4 / Apprentice-Release4.iso / Utilities / Programming / EnterAct 3.5 / hAWK project / AWK Source / ARRAY.C < prev    next >
Encoding:
C/C++ Source or Header  |  1994-12-22  |  7.3 KB  |  287 lines  |  [TEXT/TOPC]
  1. /*
  2.  * array.c - routines for associative arrays.
  3.  */
  4.  
  5. /* Copyright © 1986, 1988, 1989 1991 the Free Software Foundation, Inc.
  6.  *         This file is part of GAWK, the GNU implementation of the
  7.  * AWK Progamming Language, modified for the Macintosh (also called hAWK).
  8.  *         GAWK is free software; you can redistribute or modify
  9.  * it under the terms of the GNU General Public License as published by
  10.  * the Free Software Foundation; either version 1, or any later version.
  11.  *         GAWK is distributed in the hope that it will be useful,
  12.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  14.  * GNU General Public License for more details.
  15.  *         You should have received a copy of the GNU General Public License
  16.  * along with GAWK; see the file "COPYING hAWK". If not, write to
  17.  * the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  18.  * Modified for THINK C 4 on the Macintosh by Ken Earle (Dynabyte) Aug 1991.
  19.  */
  20. /* Mac note, only change is addition of assoc_scan_sort and assoc_next_sort. */
  21. #include "AWK.H"
  22.  
  23. /* Presumably an enticement to make the hash size variable
  24. -no one got around to it yet...*/
  25. #ifdef DONTDEF
  26. short primes[] = {31, 61, 127, 257, 509, 1021, 2053, 4099, 8191, 16381};
  27. #endif
  28.  
  29. #define ASSOC_HASHSIZE 1021
  30. #define STIR_BITS(n) ((n) << 5 | (((n) >> 27) & 0x1f))
  31. #define HASHSTEP(old, c) ((old << 1) + c)
  32. #define MAKE_POS(v) (v & ~0x80000000)    /* make number positive */
  33.  
  34. /* ARRAY.C */
  35. NODE *concat_exp(NODE *tree);
  36. void assoc_clear(NODE *symbol);
  37. static short hash_calc(NODE *subs);
  38. static NODE *assoc_find(NODE *symbol, NODE *subs, short hash1);
  39. short in_array(NODE *symbol, NODE *subs);
  40. NODE **assoc_lookup(NODE *symbol, NODE *subs);
  41. void do_delete(NODE *symbol, NODE *tree);
  42. struct search *assoc_scan(NODE *symbol);
  43. struct search *assoc_next(struct search *lookat);
  44. struct search *assoc_scan_sort(NODE *symbol);
  45. struct search *assoc_next_sort(struct search *lookat);
  46.  
  47. NODE *concat_exp(NODE *tree)
  48. {
  49.     NODE *r;
  50.     char *str;
  51.     char *s;
  52.     unsigned len;
  53.     short offset;
  54.     short subseplen;
  55.     char *subsep;
  56.  
  57.     if (tree->type != Node_expression_list)
  58.         return force_string(tree_eval(tree));
  59.     r = force_string(tree_eval(tree->lnode));
  60.     if (tree->rnode == NULL)
  61.         return r;
  62.     subseplen = SUBSEP_node->lnode->stlen;
  63.     subsep = SUBSEP_node->lnode->stptr;
  64.     len = r->stlen + subseplen + 1;
  65.     emalloc(str, char *, len, "concat_exp");
  66.     memcpy(str, r->stptr, r->stlen+1);
  67.     s = str + r->stlen;
  68.     free_temp(r);
  69.     tree = tree->rnode;
  70.     while (tree) {
  71.         if (subseplen == 1)
  72.             *s++ = *subsep;
  73.         else {
  74.             memcpy(s, subsep, subseplen+1);
  75.             s += subseplen;
  76.         }
  77.         r = force_string(tree_eval(tree->lnode));
  78.         len += r->stlen + subseplen;
  79.         offset = (short)(s - str);
  80.         erealloc(str, char *, len, "concat_exp");
  81.         s = str + offset;
  82.         memcpy(s, r->stptr, r->stlen+1);
  83.         s += r->stlen;
  84.         free_temp(r);
  85.         tree = tree->rnode;
  86.     }
  87.     r = tmp_string(str, (short)(s - str));
  88.     free(str);
  89.     return r;
  90. }
  91.  
  92. /* Flush all the values in symbol[] before doing a split() */
  93. void assoc_clear(NODE *symbol)
  94. {
  95.     short i;
  96.     NODE *bucket, *next;
  97.  
  98.     if (symbol->var_array == 0)
  99.         return;
  100.     for (i = 0; i < ASSOC_HASHSIZE; i++) {
  101.         for (bucket = symbol->var_array[i]; bucket; bucket = next) {
  102.             next = bucket->ahnext;
  103.             deref = bucket->ahname;
  104.             do_deref();
  105.             deref = bucket->ahvalue;
  106.             do_deref();
  107.             freenode(bucket);
  108.         }
  109.         symbol->var_array[i] = 0;
  110.     }
  111. }
  112.  
  113. /*
  114.  * calculate the hash function of the string subs, also returning in *typtr
  115.  * the type (string or number) 
  116.  */
  117. static short hash_calc(NODE *subs)
  118. {
  119.     register short hash1 = 0, i;
  120.  
  121.     subs = force_string(subs);
  122.     for (i = 0; i < subs->stlen; i++)
  123.         hash1 = HASHSTEP(hash1, subs->stptr[i]);
  124.  
  125.     hash1 = MAKE_POS(STIR_BITS((short) hash1)) % ASSOC_HASHSIZE;
  126.     return (hash1);
  127. }
  128.  
  129. /*
  130.  * locate symbol[subs], given hash of subs and type 
  131.  */
  132. static NODE *                /* NULL if not found */
  133. assoc_find(NODE *symbol, NODE *subs, short hash1)
  134. {
  135.     register NODE *bucket;
  136.  
  137.     for (bucket = symbol->var_array[hash1]; bucket; bucket = bucket->ahnext) {
  138.         if (cmp_nodes(bucket->ahname, subs))
  139.             continue;
  140.         return bucket;
  141.     }
  142.     return NULL;
  143. }
  144.  
  145. /*
  146.  * test whether the array element symbol[subs] exists or not 
  147.  */
  148. short in_array(NODE *symbol, NODE *subs)
  149. {
  150.     register short hash1;
  151.  
  152.     if (symbol->type == Node_param_list)
  153.         symbol = stack_ptr[symbol->param_cnt];
  154.     if (symbol->var_array == 0)
  155.         return 0;
  156.     subs = concat_exp(subs);
  157.     hash1 = hash_calc(subs);
  158.     if (assoc_find(symbol, subs, hash1) == NULL) {
  159.         free_temp(subs);
  160.         return 0;
  161.     } else {
  162.         free_temp(subs);
  163.         return 1;
  164.     }
  165. }
  166.  
  167. /*
  168.  * SYMBOL is the address of the node (or other pointer) being dereferenced.
  169.  * SUBS is a number or string used as the subscript. 
  170.  *
  171.  * Find SYMBOL[SUBS] in the assoc array.  Install it with value "" if it
  172.  * isn't there. Returns a pointer ala get_lhs to where its value is stored 
  173.  */
  174. NODE **assoc_lookup(NODE *symbol, NODE *subs)
  175. {
  176.     register short hash1, i;
  177.     register NODE *bucket;
  178.  
  179.     hash1 = hash_calc(subs);
  180.  
  181.     if (symbol->var_array == 0) {    /* this table really should grow
  182.                      * dynamically */
  183.         emalloc(symbol->var_array, NODE **, (sizeof(NODE *) *
  184.             ASSOC_HASHSIZE), "assoc_lookup");
  185.         for (i = 0; i < ASSOC_HASHSIZE; i++)
  186.             symbol->var_array[i] = 0;
  187.         symbol->type = Node_var_array;
  188.     } else {
  189.         bucket = assoc_find(symbol, subs, hash1);
  190.         if (bucket != NULL) {
  191.             free_temp(subs);
  192.             return &(bucket->ahvalue);
  193.         }
  194.     }
  195.     bucket = newnode(Node_ahash);
  196.     bucket->ahname = dupnode(subs);
  197.     bucket->ahvalue = Nnull_string;
  198.     bucket->ahnext = symbol->var_array[hash1];
  199.     symbol->var_array[hash1] = bucket;
  200.     return &(bucket->ahvalue);
  201. }
  202.  
  203. void do_delete(NODE *symbol, NODE *tree)
  204. {
  205.     register short hash1;
  206.     register NODE *bucket, *last;
  207.     NODE *subs;
  208.  
  209.     if (symbol->var_array == 0)
  210.         return;
  211.     subs = concat_exp(tree);
  212.     hash1 = hash_calc(subs);
  213.  
  214.     last = NULL;
  215.     for (bucket = symbol->var_array[hash1]; bucket; last = bucket, bucket = bucket->ahnext)
  216.         if (cmp_nodes(bucket->ahname, subs) == 0)
  217.             break;
  218.     free_temp(subs);
  219.     if (bucket == NULL)
  220.         return;
  221.     if (last)
  222.         last->ahnext = bucket->ahnext;
  223.     else
  224.         symbol->var_array[hash1] = bucket->ahnext;
  225.     deref = bucket->ahname;
  226.     do_deref();
  227.     deref = bucket->ahvalue;
  228.     do_deref();
  229.     freenode(bucket);
  230. }
  231.  
  232. struct search *assoc_scan(NODE *symbol)
  233. {
  234.     struct search *lookat;
  235.  
  236.     if (!symbol->var_array)
  237.         return 0;
  238.     emalloc(lookat, struct search *, sizeof(struct search), "assoc_scan");
  239.     lookat->numleft = ASSOC_HASHSIZE;
  240.     lookat->arr_ptr = symbol->var_array;
  241.     lookat->bucket = symbol->var_array[0];
  242.     return assoc_next(lookat);
  243. }
  244.  
  245. struct search *assoc_next(struct search *lookat)
  246. {
  247.     for (; lookat->numleft; lookat->numleft--) {
  248.         while (lookat->bucket != 0) {
  249.             lookat->retval = lookat->bucket->ahname;
  250.             lookat->bucket = lookat->bucket->ahnext;
  251.             return lookat;
  252.         }
  253.         lookat->bucket = *++(lookat->arr_ptr);
  254.     }
  255.     free((char *) lookat);
  256.     return 0;
  257. }
  258.  
  259. struct search *assoc_scan_sort(NODE *symbol)
  260. {
  261.     struct search *lookat;
  262.  
  263.     if (!symbol->var_array)
  264.         return 0;
  265.     emalloc(lookat, struct search *, sizeof(struct search), "assoc_scan");
  266.     lookat->numleft = ASSOC_HASHSIZE;
  267.     lookat->arr_ptr = symbol->var_array;
  268.     lookat->bucket = symbol->var_array[0];
  269.     return assoc_next_sort(lookat);
  270. }
  271.  
  272.  
  273. struct search *assoc_next_sort(struct search *lookat)
  274. {
  275.     for (; lookat->numleft; lookat->numleft--) {
  276.         while (lookat->bucket != 0) {
  277.             lookat->retval = lookat->bucket/*->ahname*/;
  278.             lookat->bucket = lookat->bucket->ahnext;
  279.             return lookat;
  280.         }
  281.         lookat->bucket = *++(lookat->arr_ptr);
  282.     }
  283.     free((char *) lookat);
  284.     return 0;
  285. }
  286.  
  287.